/*****************************************************
Copyright (C) 2020. All rights reserved.
File name     ：BTree.c
Version       ：v1.0
Author        ：zhengqijun
Date          ：2020-05-04
Function List ：
Description   ：B-Tree
******************************************************/

#include "BTree.h"
#include <stdlib.h>  // for malloc
#include "FatalError.h"
#include "LinkedQueue.h"

#define M   4

struct BNode {
    int          NumKeys;
    ElementType *Keys;
    Position     Parent;
    Position    *Children;
};

// Static Function Lists
static BTree SolveOverflow(Position P, BTree T);
static BTree SolveUnderflow(Position P, BTree T);

// Static Variable Lists
static Position FindPtr = NULL;

BTree MakeEmpty(BTree T) {
    int i;

    if (T != NULL) {
        for (i = 0; i < T->NumKeys + 1; ++i) {
            MakeEmpty(T->Children[i]);
        }

        free(T->Keys);
        free(T);
    }

    return NULL;
}

int IsEmpty(BTree T) {
    return T == NULL;
}

int IsLeaf(BTree T) {
    return T->Children[0] == NULL;
}

Position Find(ElementType Key, BTree T) {
    Position P;
    int Index;

    P = T;
    while (P != NULL) {
        Index = FindIndex(Key, P);
        if (Key == P->Keys[Index]) {
            return P;
        } else {
            FindPtr = P;
            P = P->Children[Index];
        }
    }

    return NULL;
}

int FindIndex(ElementType Key, Position P) {
    int Index;
    int i;

    Index = 0;
    for (i = 0; i < P->NumKeys; ++i) {
        if (Key > P->Keys[i]) {
            Index = i + 1;
        } else {
            break;
        }
    }

    return Index;
}

Position FindMin(BTree T) {
    if (T != NULL) {
        while (T->Children[0] != NULL) {
            T = T->Children[0];
        }
    }

    return T;
}

Position FindMax(BTree T) {
    if (T != NULL) {
        while (T->Children[T->NumKeys] != NULL) {
            T = T->Children[T->NumKeys];
        }
    }

    return T;
}

ElementType RetrieveMin(Position P) {
    return P->Keys[0];
}

ElementType RetrieveMax(Position P) {
    return P->Keys[P->NumKeys - 1];
}

static BTree SolveOverflow(Position P, BTree T) {
    Position Tmp;
    Position Parent;
    Position Sibling;
    int Index;
    int Mid;
    int i;
    int j;

    Mid = M / 2;
    Tmp = P;
    while (Tmp != NULL && Tmp->NumKeys == M) {
        Parent = Tmp->Parent;

        Sibling = (Position)malloc(sizeof(struct BNode));
        if (Sibling == NULL) {
            FatalError("Out of space!!!");
        } else {
            Sibling->Keys = (ElementType *)malloc(M * sizeof(ElementType));
            if (Sibling->Keys == NULL) {
                FatalError("Out of space!!!");
            } else {
                for (i = Mid + 1, j = 0; i < M; ++i) {
                    Sibling->Keys[j++] = Tmp->Keys[i];
                }

                Sibling->NumKeys = j;
                Tmp->NumKeys = Mid;
            }

            Sibling->Children = (Position *)malloc((M + 1) * sizeof(Position));
            if (Sibling->Children == NULL) {
                FatalError("Out of space!!!");
            } else {
                for (i = 0; i < M + 1; ++i) {
                    Sibling->Children[i] = NULL;
                }

                for (i = Mid + 1, j = 0; i < M + 1; ++i, ++j) {
                    Sibling->Children[j] = Tmp->Children[i];
                    Tmp->Children[i] = NULL;
                    if (Sibling->Children[j] != NULL) {
                        // Update parent of children
                        Sibling->Children[j]->Parent = Sibling;
                    }
                }
            }
        }

        if (Parent == NULL) {
            Parent = (Position)malloc(sizeof(struct BNode));
            if (Parent == NULL) {
                FatalError("Out of space!!!");
            } else {
                Parent->Keys = (ElementType *)malloc(M * sizeof(ElementType));
                if (Parent->Keys == NULL) {
                    FatalError("Out of space!!!");
                } else {
                    Parent->Keys[0] = Tmp->Keys[Mid];
                    Parent->NumKeys = 1;
                }

                Parent->Children = (Position *)malloc((M + 1) * sizeof(Position));
                if (Parent->Children == NULL) {
                    FatalError("Out of space!!!");
                } else {
                    Parent->Parent = NULL;
                    Parent->Children[0] = Tmp;
                    Parent->Children[1] = Sibling;
                    for (i = 2; i < M + 1; ++i) {
                        Parent->Children[i] = NULL;
                    }
                }

                T = Parent;
                Tmp->Parent = Parent;
            }
        } else {
            Index = FindIndex(Tmp->Keys[Mid], Parent);
            for (i = Parent->NumKeys; i > Index; --i) {
                Parent->Keys[i] = Parent->Keys[i - 1];
            }

            for (i = Parent->NumKeys + 1; i > Index + 1; --i) {
                Parent->Children[i] = Parent->Children[i - 1];
            }

            ++Parent->NumKeys;
            Parent->Keys[Index] = Tmp->Keys[Mid];
            Parent->Children[Index + 1] = Sibling;
        }

        Sibling->Parent = Parent;
        Tmp = Tmp->Parent;
    }

    return T;
}

static BTree SolveUnderflow(Position P, BTree T) {
    Position Tmp;
    Position Parent;
    Position Sibling;
    int i;
    int j;
    int Min;
    int Index;

    Min = (M + 1) / 2 - 1;
    Tmp = P;
    while (Tmp != NULL) {
        /* Underflow occurs */
        if (Tmp->NumKeys < Min) {
            Parent = Tmp->Parent;
            Index = 0;
            while (Parent->Children[Index] != Tmp) {
                ++Index;
            }

            /* Borrow from the left brother */
            if (Index != 0) {
                Sibling = Parent->Children[Index - 1];
                if (Sibling->NumKeys > Min) {
                    for (i = Tmp->NumKeys; i > 0; --i) {
                        Tmp->Keys[i] = Tmp->Keys[i - 1];
                    }

                    for (i = Tmp->NumKeys + 1; i > 0; --i) {
                        Tmp->Children[i] = Tmp->Children[i - 1];
                    }

                    Tmp->Keys[0] = Parent->Keys[Index - 1];
                    ++Tmp->NumKeys;
                    Tmp->Children[0] = Sibling->Children[Sibling->NumKeys];
                    if (Tmp->Children[0] != NULL) {
                        Tmp->Children[0]->Parent = Tmp;
                    }

                    Parent->Keys[Index - 1] = Sibling->Keys[Sibling->NumKeys - 1];
                    --Sibling->NumKeys;

                    break;
                }
            }

            /* Borrow from the right brother */
            if (Index != Parent->NumKeys) {
                Sibling = Parent->Children[Parent->NumKeys];
                if (Sibling->NumKeys > Min) {
                    Tmp->Keys[Tmp->NumKeys] = Parent->Keys[Index];
                    ++Tmp->NumKeys;
                    Tmp->Children[Tmp->NumKeys] = Sibling->Children[0];
                    if (Tmp->Children[Tmp->NumKeys] != NULL) {
                        Tmp->Children[Tmp->NumKeys]->Parent = Tmp;
                    }

                    Parent->Keys[Index] = Sibling->Keys[0];
                    for (i = 0; i < Sibling->NumKeys - 1; ++i) {
                        Sibling->Keys[i] = Sibling->Keys[i + 1];
                    }

                    for (i = 0; i < Sibling->NumKeys; ++i) {
                        Sibling->Children[i] = Sibling->Children[i + 1];
                    }

                    --Sibling->NumKeys;

                    break;
                }
            }

            /* Merge left and right brothers */
            if (Index > 0) {
                Sibling = Parent->Children[Index - 1];

                // Update children
                Sibling->Keys[Sibling->NumKeys] = Parent->Keys[Index - 1];
                j = Sibling->NumKeys + 1;
                for (i = 0; i < Tmp->NumKeys; ++i) {
                    Sibling->Keys[j++] = Tmp->Keys[i];
                }

                j = Sibling->NumKeys + 1;
                for (i = 0; i < Tmp->NumKeys + 1; ++i, ++j) {
                    Sibling->Children[j] = Tmp->Children[i];
                    if (Sibling->Children[j] != NULL) {
                        // Update parent of children
                        Sibling->Children[j]->Parent = Sibling;
                    }
                }

                Sibling->NumKeys += Tmp->NumKeys + 1;

                // Update parent
                for (i = Index - 1; i < Parent->NumKeys - 1; ++i) {
                    Parent->Keys[i] = Parent->Keys[i + 1];
                }

                for (i = Index; i < Parent->NumKeys; ++i) {
                    Parent->Children[i] = Parent->Children[i + 1];
                }

                --Parent->NumKeys;

                free(Tmp->Children);
                free(Tmp->Keys);
                free(Tmp);
            } else {
                Sibling = Parent->Children[Index + 1];

                // Update children
                Tmp->Keys[Tmp->NumKeys] = Parent->Keys[Index];
                j = Tmp->NumKeys + 1;
                for (i = 0; i < Sibling->NumKeys; ++i) {
                    Tmp->Keys[j++] = Sibling->Keys[i];
                }

                j = Tmp->NumKeys + 1;
                for (i = 0; i < Sibling->NumKeys + 1; ++i, ++j) {
                    Tmp->Children[j] = Sibling->Children[i];
                    if (Tmp->Children[j] != NULL) {
                        // Update parent of children
                        Tmp->Children[j]->Parent = Tmp;
                    }
                }

                Tmp->NumKeys += Sibling->NumKeys + 1;

                // Update parent
                for (i = Index; i < Parent->NumKeys; ++i) {
                    Parent->Keys[i] = Parent->Keys[i + 1];
                }

                for (i = Index + 1; i < Parent->NumKeys; ++i) {
                    Parent->Children[i] = Parent->Children[i + 1];
                }

                --Parent->NumKeys;

                free(Sibling->Children);
                free(Sibling->Keys);
                free(Sibling);
            }

            if (Parent->Parent == NULL && Parent->NumKeys == 0) {
                /* Delete root */
                T = Parent->Children[0];
                T->Parent = NULL;

                free(Parent->Keys);
                free(Parent->Children);
                free(Parent);

                break;
            } else {
                Tmp = Parent;
            }
        } else {
            break;
        }
    }

    return T;
}

BTree Insert(ElementType Key, BTree T) {
    int i;

    if (T == NULL) {
        /* Create and return a one-node tree */
        T = (BTree)malloc(sizeof(struct BNode));
        if (T == NULL) {
            FatalError("Out of space!!!");
        } else {
            T->Keys = (ElementType *)malloc(M * sizeof(ElementType));
            if (T->Keys == NULL) {
                FatalError("Out of space!!!");
            }

            T->Children = (Position *)malloc((M + 1) * sizeof(Position));
            if (T->Children == NULL) {
                FatalError("Out of space!!!");
            } else {
                for (i = 0; i < M + 1; ++i) {
                    T->Children[i] = NULL;
                }
            }

            T->Keys[0] = Key;
            T->NumKeys = 1;
            T->Parent = NULL;
        }
    } else {
        Position P;
        int Index;

        P = Find(Key, T);
        if (P == NULL) {
            Index = FindIndex(Key, FindPtr);
            for (i = FindPtr->NumKeys; i > Index; --i) {
                FindPtr->Keys[i] = FindPtr->Keys[i - 1];
            }

            FindPtr->Keys[Index] = Key;
            ++FindPtr->NumKeys;

            T = SolveOverflow(FindPtr, T);
        }
    }

    return T;  /* Do not forget this line!! */
}

BTree Delete(ElementType Key, BTree T) {
    if (T != NULL) {
        Position P;
        Position C;
        int Index;
        int i;

        P = Find(Key, T);
        if (P != NULL) {
            Index = FindIndex(Key, P);
            /* Convert the deletion of non-leaf nodes */
            /* to deletion of leaf nodes */
            if (P->Children[0] != NULL) {
                /* Find the largest element in the left subtree */
                C = P->Children[Index + 1];
                while (C->Children[0] != NULL) {
                    C = C->Children[0];
                }

                P->Keys[Index] = C->Keys[0];
                P = C;
                Index = 0;
            }

            --P->NumKeys;  /* Update the number of key */
            for (i = Index; i < P->NumKeys; ++i) {
                P->Keys[i] = P->Keys[i + 1];
            }   

            T = SolveUnderflow(P, T);
        }
    }

    return T;  /* Do not forget this line!! */
}

void PrintBTree(BTree T) {
    if (T != NULL) {
        LinkedQueue Q;
        int Cur;
        int Next;
        int Index;
        int i;

        Q = CreateQueue();

        EnQueue(T, Q);
        Next = 0;
        Cur = 1;
        Index = 0;

        while (!IsEmptyQueue(Q)) {
            for (i = 0; i < Front(Q)->NumKeys + 1; ++i) {
                if (Front(Q)->Children[i] != NULL) {
                    EnQueue(Front(Q)->Children[i], Q);
                    Next += 1;
                }
            }

            for (i = 0; i < Front(Q)->NumKeys - 1; ++i) {
                printf("%02d ", Front(Q)->Keys[i]);
            }

            if (Front(Q)->NumKeys > 0) {
                if (Front(Q)->Parent != NULL) {
                    printf("%02d[%02d]", Front(Q)->Keys[i], Front(Q)->Parent->Keys[0]);
                } else {
                    printf("%02d", Front(Q)->Keys[i]);
                }
            }

            ++Index;
            if (Index == Cur) {
                Cur = Next;
                Next = 0;
                Index = 0;
                printf("\n");
            } else {
                printf("    ");
            }

            DeQueue(Q);
        }
    }
}

// EOF

